1. Field of the Invention
This invention relates to the field of computer graphics, and, more specifically, to graphical rendering of surfaces.
2. Background Art
In computer graphics, images are often created from three-dimensional objects modeled within a computer. The process of transforming the three-dimensional object data within the computer into viewable images is referred to as rendering. Typically, objects are modeled as one or more surfaces. Ideally, these surfaces comprise continuous curves for best visual realism. However, in practice, these surfaces are approximated with a mesh of less complex surface components, such as parametric surfaces or patches, to reduce the computational complexity of the rendering process. These patches are further subdivided or xe2x80x9cdicedxe2x80x9d into triangles or polygons for rendering purposes. For example, bicubic patches are often rendered by subdividing their parameter space into rectangular grid of quadrilaterals, which are then further subdivided into triangles for rendering. A higher dicing rate provides greater modeling resolution and a better surface approximation. The dicing rate of a given patch may depend on factors such as the distance of the patch from the viewing plane and the local feature complexity of the patch.
An undesirable phenomenon known as xe2x80x9ccrackingxe2x80x9d occurs when surfaces are split into multiple patches that are rendered independently. The shared boundaries between patches are tessellated and displaced by each side independently, which often creates narrow gaps or xe2x80x9ccracksxe2x80x9d between the two sides. Adjacent patches can compute different positions for their shared boundary curve for several reasons:
Two adjacent patches may dice at different rates, generating different numbers of vertices along a shared edge.
The adjacent patches may compute different positions for a vertex at the same parametric location, due to numerical errors. For example, this can occur if one patch has split into two pieces along the adjacent edge while the other patch has not.
Vertices along a shared edge may have different positions in the two patches due to displacement mapping (a technique whereby the diced vertex positions are modified according to a given formula, such as a texture map lookup, in order to add geometric detail to a smooth underlying surface). For example, this can happen when finite difference techniques are used in the displacement calculations (to estimate surface normals, derivatives, or texture filtering information). This is because finite difference techniques cause the position of a vertex to depend on the position of its neighbors, which are different in the two patch tessellations.
An example of crack formation is illustrated in FIGS. 1A and 1B. FIG. 1A depicts an idealized surface comprising regions 100 and 101, having a continuous seam 102 between the regions. FIG. 1B depicts an approximation of the surface of FIG. 1A, wherein region 100 is now 100A comprising several parametric surfaces with piecewise linear edge 102A corresponding to seam 102. Similarly, region 101A comprises several parametric surfaces having piecewise linear edge 102B corresponding to seam 102. Edge 102A models seam 102 with a higher dicing rate than edge 102B. As shown, edge 102A contains four vertices within the same span in which edge 102B has three vertices. The mismatch in dicing rates as well as the displacement differences between vertices in edges 102A and 102B form a crack 103 between regions 100A and 101A. Crack 103 represents a rendering error that may be visually apparent in the final rendered image, particularly where there is high contrast between the color value associated with regions 100B and 101B and the color value associated with the background visible through the crack.
Previous techniques for eliminating cracks fall into several categories. First there are methods that render parametric surfaces as a restricted quad-tree. That is, tessellation is limited to a pattern of quadrilaterals wherein the variation in dicing rates between patches is strictly constrained. These techniques store the entire tessellated surface in memory and do not support surfaces of arbitrary topology.
A second set of techniques are based on the idea that the tessellation of a boundary should be based only on the boundary curve itself. However, these methods do not eliminate all sources of cracking. In particular, if the patches on one side of a shared boundary have split more often than those on the other, then there is no single dicing rate for the unsplit patch that can match the multiple rates on the other side. Furthermore these techniques cannot handle the problems caused by displacement mapping, in which case the two sides can have different vertex positions even if the dicing rates match.
In another variation, the boundary curves are tessellated before patches are split. This technique has several drawbacks. It generates highly irregular tessellations that cannot be evaluated efficiently; it requires a substantial amount of time and memory to split patches that may eventually be occluded (and discarded) anyway; and, furthermore, this technique cannot render patches whose boundaries are simple (e.g. flat) but have complex features in their interiors.
Finally, some prior art techniques are based on the idea of splitting all patches and determining dicing rates in a preprocessing phase. For each portion of a shared boundary edge, one of the two adjacent patches is arbitrarily chosen to be associated with that edge. The main drawback to this approach is that the entire surface must be tessellated (or at least all dicing rates must be determined) in advance, which has significant time and memory expenses.
A method and apparatus for surface approximation without cracks are described. Embodiments of the invention may be applied to surfaces of arbitrary topology. In one or more embodiments, a surface to be rendered is split into multiple adjacent regions (e.g., subdivision surfaces or patches). A data structure is associated with each boundary edge between two regions for storage of adjacency information in the form of a sequence of tessellation vertices. Adjacency information for a given edge is written into the data structure when an adjacent region is first tessellated. When the remaining adjacent region is tessellated, the adjacency information is read from the data structure and used to achieve tessellation without cracks. In one embodiment, visible cracks due to T-vertices are prevented by forming an overlap of adjacent regions at the location of each T-vertex. This technique allows regions to be tessellated and rendered without any advance knowledge of how the adjacent regions will be split. The regions may be tessellated and rendered separately and in any order, reducing time and memory requirements for rendering.
In one embodiment, the data structure is implemented as a binary tree having a root node created when a new edge is created through a splitting operation. Splitting of an existing edge results in the creation of two child nodes corresponding to the new edge segments. Nodes may be freed from memory when no longer referenced by either of the associated adjacent regions.